\input{euler.tex}

%\textstyle - default in the running text and in array environment 
%\displaystyle - default for displayed equations

\begin{document}

\problem[40]{Finding the Nth Digit of a Fractional Number}

An irrational decimal fraction is created by concatenating the positive integers:
\[
0.123456789101112131415161718192021...
\]
It can be seen that the 12th digit of the fractional part is 1.

If $d_n$ represents the $n$th digit of the fractional part, find the value of the following expression.
\[ 
d_1 \times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000} .
\]

\solution

We can group the fractional part by the number of digits in the integers that are concatenated, as below:
\[
0.(1 \ldots 9)(10 \ldots 99)(100 \ldots 999) \ldots 
\]
It can be seen that there are 9 single-digit numbers, 90 double-digit numbers, 900 triple-digit numbers, etc.

Let $b$ be the base of the number. Let $a_k$ be the number of digits in the $k$-digit group. Let $s_k$ be total number of digits from the beginning of the fraction up to the end of the $k$-digit group. We then have
\begin{align}
a_k &= (b-1) \cdot k \cdot b^{k-1} \notag \\
s_k &= s_{k-1}+a_k \notag \\
s_0 &= 0 \notag
\end{align}

To find the $n$-th digit $d_n$, first locate $k$ such that
\[
s_{k-1} < n \le s_{k}.
\]
That is, the $n$-th digit comes from a $k$-digit group. Let $m$ be the integer that the digit comes from, $i$ be the zero-based index of $m$ in the group, and $p$ be the position of the digit in $m$. Then we have
\begin{align}
i &= \lfloor (n-s_{k-1}-1)/k \rfloor \notag \\
m &= b^{k-1} + i \notag \\
p &= n - s_{k-1} - ik \notag 
\end{align}
It follows that $d_n$ is the $p$-th digit in $m$.

Apply these formula to the problem, and we find the digits are 1, 1, 5, 3, 7, 2, 1.

\answer

210

\complexity

Time complexity: $\BigO(\log_b N)$

Space complexity: $\BigO(1)$

\end{document} 